/*
 * @lc app=leetcode.cn id=90 lang=javascript
 *
 * [90] 子集 II
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function (nums) {
  // 不能包含重复的子集，需要先排序。
  // 类似122和212属于相同子集
  nums.sort((a, b) => a - b);
  const result = [];
  // 保存已经获得的子集
  const memo = new Map();
  /**
   * @description:
   * @param {[number]} nums
   * @param {number} start
   * @param {[number]} track
   * @return {void}
   */
  const backtrack = (nums, start, track) => {
    if (memo.has(track.toString())) {
      return;
    }
    // 这里需要push的track的拷贝
    result.push([...track]);
    memo.set(track.toString(), 1);
    for (let i = start; i < nums.length; i++) {
      // 选择
      track.push(nums[i]);
      // 回溯
      backtrack(nums, i + 1, track);
      // 撤销选择
      track.pop();
    }
  };
  backtrack(nums, 0, []);
  return result;
};
// @lc code=end
